//import com.sun.org.apache.regexp.internal.RE;
//import sun.reflect.generics.tree.Tree;
//
//import java.time.OffsetDateTime;
//import java.util.*;
//
///**
// * @Author 12629
// * @Description：
// */
//
//
//public class BinaryTree {
//    static class TreeNode {
//        public char val;
//        public TreeNode left;
//        public TreeNode right;
//
//        public TreeNode(char val) {
//            this.val = val;
//        }
//    }
//
//
//    public TreeNode createTree() {
//        TreeNode A = new TreeNode('A');
//        TreeNode B = new TreeNode('B');
//        TreeNode C = new TreeNode('C');
//        TreeNode D = new TreeNode('D');
//        TreeNode E = new TreeNode('E');
//        TreeNode F = new TreeNode('F');
//        TreeNode G = new TreeNode('G');
//        TreeNode H = new TreeNode('H');
//        A.left = B;
//        A.right = C;
//        B.left = D;
//        B.right = E;
//        C.left = F;
//        C.right = G;
//        E.right = H;
//        return A;
//    }
//
//    public void preOrder(TreeNode root) {
//        if(root == null) return;//或return返回
//        System.out.print(root.val+" ");
//        preOrder(root.left);
//        preOrder(root.right);
//    }//在}结束返回
//    /**
//     * 将前序遍历的结果 存储到list当中
//     * @param root
//     * @return
//     */
//    List<TreeNode> ret = new ArrayList<>();
//    public List<TreeNode> preOrder3(TreeNode root) {
//        if(root == null) return ret;
//        //System.out.print(root.val+" ");
//        ret.add(root);
//        preOrder3(root.left);
//        preOrder3(root.right);
//        return ret;
//    }
//
//    public List<TreeNode> preOrder2(TreeNode root) {
//        List<TreeNode> ret = new ArrayList<>();
//        if(root == null) return ret;
//        ret.add(root);
//        List<TreeNode> leftTree = preOrder2(root.left);
//        ret.addAll(leftTree);
//        List<TreeNode> rightTree = preOrder2(root.right);
//        ret.addAll(rightTree);
//        return ret;
//    }
//
//    public void inOrder(TreeNode root) {
//        if(root == null) return;
//        inOrder(root.left);
//        System.out.print(root.val+" ");
//        inOrder(root.right);
//    }
//
//    public List<Character> inorderTraversal(TreeNode root) {
//        List<Character> ret = new ArrayList<>();
//        if(root == null) return ret;
//
//        List<Character> leftTree = inorderTraversal(root.left);
//        ret.addAll(leftTree);
//
//
//        ret.add(root.val);
//
//        List<Character> rightTree = inorderTraversal(root.right);
//        ret.addAll(rightTree);
//
//        return ret;
//    }
//
//    public void postOrder(TreeNode root) {
//        if(root == null) return;
//        postOrder(root.left);
//        postOrder(root.right);
//        System.out.print(root.val+" ");
//    }
//
//    public List<Character> postorderTraversal(TreeNode root) {
//        List<Character> ret = new ArrayList<>();
//        if(root == null) return ret;
//
//        List<Character> leftTree = postorderTraversal(root.left);
//        ret.addAll(leftTree);
//
//
//        List<Character> rightTree = postorderTraversal(root.right);
//        ret.addAll(rightTree);
//
//        ret.add(root.val);
//
//        return ret;
//    }
//
//
//    public int size = 0;
//    public void nodeSize(TreeNode root) {
//        if(root == null) return ;
//        size++;
//        nodeSize(root.left);
//
//        nodeSize(root.right);
//
//    }
//
//    public int nodeSize2(TreeNode root) {
//        if(root == null) return 0;
//
//        return nodeSize2(root.left)+
//                nodeSize2(root.right) + 1;
//    }
//
//    public int leafSize = 0;
//    public void getLeafSize(TreeNode root) {
//        if(root == null) return;
//        if(root.left == null && root.right == null) {
//            leafSize++;
//        }
//        getLeafSize(root.left);
//        getLeafSize(root.right);
//    }
//
//    /**
//     * 使用子问题
//     * @param root
//     * @return
//     */
//    public int getLeafSize2(TreeNode root) {
//        if(root == null) return 0;
//        if(root.left == null && root.right == null) {
//            return 1;
//        }
//
//        return getLeafSize2(root.left)+
//                getLeafSize2(root.right);
//    }
//
//    /**
//     * 第K层节点的个数
//     * @param root
//     * @return
//     */
//    public int getKLevelNodeCount(TreeNode root,int k) {
//        if(root == null) return 0;
//        if(k == 1) {
//            return 1;
//        }
//        return getKLevelNodeCount(root.left, k-1) +
//                getKLevelNodeCount(root.right, k-1);
//    }
//
//    public int getHeight(TreeNode root) {
//        if(root == null) return 0;
//        int leftHeight = getHeight(root.left);
//        int rightHeight = getHeight(root.right);
//
//        return (leftHeight > rightHeight ?
//                leftHeight+1 : rightHeight+1);
//    }
//
//    public int getHeight2(TreeNode root) {
//        if(root == null) return 0;
//
//        return (getHeight2(root.left) > getHeight2(root.right) ?
//                getHeight2(root.left)+1 : getHeight2(root.right)+1);
//    }
//
//
//    public boolean find(TreeNode root, char key) {
//        if(root == null) {
//            return false;
//        }
//        if(root.val == key) {
//            return true;
//        }
//
//        boolean leftVal = find(root.left,key);
//        if(leftVal == true) {
//            return true;
//        }
//        boolean rightVal = find(root.right,key);
//        if(rightVal == true) {
//            return true;
//        }
//
//        return false;
//    }
//
//    /**
//     * 时间复杂度：
//     * @param p N
//     * @param q M
//     * @return
//     */
//    public boolean isSameTree(TreeNode p, TreeNode q) {
//        if(p == null && q != null || p != null && q == null ) {
//            return false;
//        }
//        //两个都为空呢？
//        if(p == null && q == null) {
//            return true;
//        }
//        //一定是两个引用 都不为空 | 两个都不为空呢？
//        if(p.val != q.val) {
//            return false;
//        }
//
//        return isSameTree(p.left,q.left) &&
//                isSameTree(p.right,q.right);
//
//    }
//
//
//    /**
//     * 时间复杂度：O(r * s)
//     * @param root   r
//     * @param subRoot   s
//     * @return
//     */
//    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
//        if(root == null) return false;
//        if(isSameTree(root,subRoot)) {
//            return true;
//        }
//        if(isSubtree(root.left,subRoot)) {
//            return true;
//        }
//        if(isSubtree(root.right,subRoot)) {
//            return true;
//        }
//        return false;
//    }
//
//    public TreeNode invertTree(TreeNode root) {
//        if(root == null) {
//            return null;
//        }
//        TreeNode tmp = root.left;
//        root.left = root.right;
//        root.right = tmp;
//
//        invertTree(root.left);
//        invertTree(root.right);
//
//        return root;
//    }
//
//    public boolean isBalanced(TreeNode root) {
//        if(root == null) {
//            return true;
//        }
//        int leftHeight = getHeight(root.left);
//        int rightHeight = getHeight(root.right);
//
//        return Math.abs(leftHeight-rightHeight) <= 1
//                && isBalanced(root.left)
//                && isBalanced(root.right);
//
//    }
//
//
//
//    public boolean isSymmetric(TreeNode root) {
//        if(root == null) {
//            return true;
//        }
//        return isSymmetricChild(root.left,root.right);
//    }
//    public boolean isSymmetricChild(TreeNode p,TreeNode q) {
//        if(p == null && q != null || p != null && q == null) {
//            return false;
//        }
//        if(p == null && q == null) {
//            return true;
//        }
//        if(p.val != q.val) {
//            return false;
//        }
//        return isSymmetricChild(p.left,q.right)
//                && isSymmetricChild(p.right,q.left);
//    }
//
//    public static  int i = 0;
//
//    public static TreeNode creatrTree(String str) {
//        TreeNode root = null;
//
//        if(str.charAt(i) != '#') {
//            root = new TreeNode(str.charAt(i));
//            i++;
//            root.left = creatrTree(str);
//            root.right = creatrTree(str);
//        }else {
//            i++;
//        }
//        return root;
//    }
//
//    public void levelOrder1(TreeNode root) {
//        if(root == null) {
//            return;
//        }
//        Queue<TreeNode> queue = new LinkedList<>();
//        queue.offer(root);
//        while (!queue.isEmpty()) {
//            TreeNode cur = queue.poll();
//            System.out.print(cur.val+" ");
//            if(cur.left != null) {
//                queue.offer(cur.left);
//            }
//            if(cur.right != null) {
//                queue.offer(cur.right);
//            }
//        }
//    }
//
//    public List<List<TreeNode>> levelOrder(TreeNode root) {
//        List<List<TreeNode>> ret = new ArrayList<>();
//        if(root == null) {
//            return ret;
//        }
//        Queue<TreeNode> queue = new LinkedList<>();
//        queue.offer(root);
//        while (!queue.isEmpty()) {
//            //求一下当前队列的大小  4
//            int size = queue.size();//4
//            List<TreeNode> tmp = new ArrayList<>();
//            while (size != 0) {
//                // 出队列4次 相当于把 这一层的节点都 出队了
//                TreeNode cur = queue.poll();
//                //System.out.print(cur.val+" ");
//                tmp.add(cur);
//                size--;//0
//                if(cur.left != null) {
//                    queue.offer(cur.left);
//                }
//                if(cur.right != null) {
//                    queue.offer(cur.right);
//                }
//            }
//            ret.add(tmp);
//        }
//        return ret;
//    }
//
//    public boolean isCompleteTree(TreeNode root) {
//        if(root == null) {
//            return true;
//        }
//        Queue<TreeNode> queue = new LinkedList<>();
//        queue.offer(root);
//        while (!queue.isEmpty()) {
//            TreeNode cur = queue.poll();
//            if(cur != null) {
//                queue.offer(cur.left);
//                queue.offer(cur.right);
//            }else {
//                //此时遇到了null
//                break;
//            }
//        }
//        while (!queue.isEmpty()) {
//            TreeNode cur = queue.poll();
//            if(cur != null) {
//                return false;
//            }
//        }
//        return true;
//    }
//
//    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
//        if(root == null) {
//            return null;
//        }
//        if(root == p || root == q) {
//            return root;
//        }
//        TreeNode leftTree = lowestCommonAncestor(root.left,p,q);
//        TreeNode rightTree = lowestCommonAncestor(root.right,p,q);
//        if(leftTree != null && rightTree != null) {
//            return root;
//        }else if(leftTree != null) {
//            return leftTree;
//        }else {
//            return rightTree;
//        }
//    }
//
//
//    /**
//     * 找到root 到 node 之间路径上 的 所有 的 节点 存储到stack中
//     *
//     * @param root
//     * @param node
//     * @param stack
//     * @return
//     */
//    private boolean getPath(TreeNode root, TreeNode node, Stack<TreeNode> stack) {
//        if(root == null || node == null) {
//            return false;
//        }
//        stack.push(root);
//        if(root == node) {
//            return true;
//        }
//        boolean flg = getPath(root.left,node,stack);
//        if(flg) {
//            return true;
//        }
//        boolean flg2 = getPath(root.right,node,stack);
//        if(flg2) {
//            return true;
//        }
//        stack.pop();
//        return false;
//    }
//
//
//    public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
//        if(root == null) {
//            return null;
//        }
//        Stack<TreeNode> stackP = new Stack<>();
//        Stack<TreeNode> stackQ = new Stack<>();
//
//        getPath(root,p,stackP);
//        getPath(root,q,stackQ);
//
//        //对栈的操作
//        int sizeP = stackP.size();
//        int sizeQ = stackQ.size();
//
//        if(sizeP > sizeQ) {
//            int size = sizeP - sizeQ;
//            while (size != 0) {
//                stackP.pop();
//                size--;
//            }
//        }else {
//            int size = sizeQ - sizeP;
//            while (size != 0) {
//                stackQ.pop();
//                size--;
//            }
//        }
//        //两个栈当中 元素的个数是相同的
//        while (!stackP.isEmpty() && !stackQ.isEmpty()) {
//            if(stackP.peek() .equals(stackQ.peek())) {
//                return stackP.peek();
//            }
//            stackP.pop();
//            stackQ.pop();
//        }
//        return null;
//    }
//
//    class Solution {
//
//
//        public int priIndex;
//
//        public TreeNode buildTree(int[] preorder, int[] inorder) {
//
//            return buildTreeChild(preorder,inorder,0,inorder.length-1);
//        }
//
//        private TreeNode buildTreeChild(int[] preorder,int[] inorder,int inbegin,int inend) {
//
//            //1. 没有左树 或者 没有右树了
//            if(inbegin > inend) {
//                return null;
//            }
//            //2.创建根节点
//            TreeNode root = new TreeNode(preorder[priIndex]);
//
//            //3.从中序遍历当中 找到根节点所在的下标
//            int rootIndex = findIndex(inorder,inbegin,inend,preorder[priIndex]);
//            if(rootIndex == -1) {
//                return null;
//            }
//
//            priIndex++;
//            //4. 创建左子树 和  右子树
//            root.left = buildTreeChild(preorder,inorder,inbegin,rootIndex-1);
//
//            root.right = buildTreeChild(preorder,inorder,rootIndex+1,inend);
//
//            return root;
//        }
//
//        private int findIndex(int[] inorder,int inbegin,int inend,int key) {
//            for(int i = inbegin;i <= inend;i++) {
//                if(inorder[i] == key) {
//                    return i;
//                }
//            }
//            return -1;
//        }
//    }
//
//    /*
//    class Solution {
//
//
//    public int postIndex ;
//    public TreeNode buildTree(int[] inorder, int[] postorder) {
//
//        postIndex = postorder.length-1;
//
//        return buildTreeChild(postorder,inorder,0,inorder.length-1);
//    }
//
//    private TreeNode buildTreeChild(int[] postorder,int[] inorder,int inbegin,int inend) {
//
//        //1. 没有左树 或者 没有右树了
//        if(inbegin > inend) {
//            return null;
//        }
//        //2.创建根节点
//        TreeNode root = new TreeNode(postorder[postIndex]);
//
//        //3.从中序遍历当中 找到根节点所在的下标
//        int rootIndex = findIndex(inorder,inbegin,inend,postorder[postIndex]);
//        if(rootIndex == -1) {
//            return null;
//        }
//
//        postIndex--;
//        //4. 创建左子树 和  右子树
//
//        root.right = buildTreeChild(postorder,inorder,rootIndex+1,inend);
//
//        root.left = buildTreeChild(postorder,inorder,inbegin,rootIndex-1);
//
//        return root;
//    }
//
//    private int findIndex(int[] inorder,int inbegin,int inend,int key) {
//        for(int i = inbegin;i <= inend;i++) {
//            if(inorder[i] == key) {
//                return i;
//            }
//        }
//        return -1;
//    }
//}
//     */
//
//    public String tree2str(TreeNode root) {
//        StringBuilder stringBuilder  = new StringBuilder();
//        tree2strChild(root,stringBuilder);
//        return stringBuilder.toString();
//    }
//
//    private void tree2strChild(TreeNode t,StringBuilder stringBuilder) {
//        if(t == null) {
//            return;
//        }
//        stringBuilder.append(t.val);
//        if(t.left != null) {
//            stringBuilder.append("(");
//            tree2strChild(t.left,stringBuilder);
//            stringBuilder.append(")");
//        }else {
//            if(t.right == null) {
//                return;
//            }else{
//                stringBuilder.append("()");
//            }
//        }
//        if(t.right != null) {
//            stringBuilder.append("(");
//            tree2strChild(t.right,stringBuilder);
//            stringBuilder.append(")");
//        }else {
//            return;
//        }
//    }
//
//    public void preOrderNor(TreeNode root) {
//        if(root == null) return;
//        Stack<TreeNode> stack = new Stack<>();
//        TreeNode cur = root;
//        TreeNode top = null;
//        while (cur != null || !stack.isEmpty()) {
//            while (cur != null) {
//                stack.push(cur);
//                System.out.print(cur.val + " ");
//                cur = cur.left;
//            }
//
//            top = stack.pop();
//            cur = top.right;
//        }
//    }
//
//    public void inOrderNor(TreeNode root) {
//        if(root == null) return;
//        Stack<TreeNode> stack = new Stack<>();
//        TreeNode cur = root;
//        TreeNode top = null;
//        while (cur != null || !stack.isEmpty()) {
//            while (cur != null) {
//                stack.push(cur);
//                cur = cur.left;
//            }
//            top = stack.pop();
//            System.out.print(top.val + " ");
//            cur = top.right;
//        }
//    }
//
//    public void postOrderNor(TreeNode root) {
//        if(root == null) return;
//        Stack<TreeNode> stack = new Stack<>();
//        TreeNode cur = root;
//        TreeNode top = null;
//        TreeNode prev = null;
//        while (cur != null || !stack.isEmpty()) {
//            while (cur != null) {
//                stack.push(cur);
//                cur = cur.left;
//            }
//            top = stack.peek();
//            if (top.right == null || top.right == prev) {
//                stack.pop();
//                System.out.print(top.val + " ");
//                prev = top;//当前这个节点 被打印了
//            }else {
//                cur = top.right;
//
//            }
//        }
//    }
//}